/**
 * @author VernHe
 * @date 2021年04月21日 16:04
 *
 * 优化空间复杂度：dp数组用byte数组或者用三个变量来进行记录(上 左 当前)
 */
public class Solution_063 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (row == 0 && col == 0) {
            return 1;
        }

        // 状态转移方程，dp[i][j]表示从起点到第i行第j列位置的走法
        int[][] dp = new int[row+1][col+1];
        // 初始化dp数组的第0行
        dp[0][1] = 1;

        // 计算dp数组
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (obstacleGrid[i-1][j-1] == 0 && i != 1 && j != 1) {
                    // 不是障碍物
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                } else {
                    // 是障碍物
                    dp[i][j] = 0;
                }
            }
        }

        return dp[row][col];
    }
}
